Sau quá trình tu học dài hạn, Phó tế Anphong Nguyễn Hữu Long đã được thụ phong linh mục ngày 29 tháng 12 năm 1990. Tân linh mục chọn cho mình châm ngôn: "Tình yêu Đức Kitô thôi thúc tôi".[15][16] Sau khi được phong chức linh mục, linh mục Long được bổ nhiệm đảm trách vai trò linh mục phó giáo xứ Tam Kỳ, Đà Nẵng. Năm 1994, ông được cho đi du học tại Pháp và tốt nghiệp Cao học Giáo luật tại Học viện Công giáo Paris. Sau quá trình du học, năm 1999, linh mục Long trở về Việt Nam và được bổ nhiệm giữ vai trò quản nhiệm giáo xứ Hà Lam, Giáo phận Đà Nẵng trong thời gian ngắn, đến năm khoảng năm 2000 - 2001. Sau đó, linh mục Long đảm nhận vai trò linh mục chính xứ giáo xứ Trà Kiệu, thuộc Giáo phận Đà Nẵng và giữ chức vụ này đến năm 2003.[10][15][17][18]

Năm 2003, linh mục Nguyễn Hữu Long gia nhập Hội Linh mục Xuân Bích (PSS). Trong khoảng tám năm, từ năm 2003 đến năm 2011, ông đảm nhận vai trò linh mục linh hướng và Giáo sư các môn: Giáo luật, Giáo sử và Huấn giáo tại Đại chủng viện Huế.[15]

Trong khoảng thời gian từ năm 2011 đến tháng 9 năm 2013, linh mục Long đảm nhận vai trò Giám đốc Đại chủng viện Huế.[15]